1. Field of the Invention
This invention relates generally to design and process verification. More particularly, this invention relates to evaluation of a process or a design for compliance with its specification.
2. Description of the Related Art
TABLE 1Acronyms and AbbreviationsCSPConstraint Satisfaction ProblemDAGDirected Acyclic GraphISAInstruction Set Architecture
Important aspects of designing a system that operates according to process sequences include the ability to test the design thoroughly, in order to assure that the design complies with desired architectural, performance and design specifications.
Test program generators are basically sophisticated software engines, which are used to create numerous test cases to be executed by the design-under-test. By appropriate configuration, it is possible for test generation to be focused on very specific ranges of conditions, or broadened to cover a wide range of logic. Today, large numbers of test cases can be created automatically in the time that a single test case could be written manually, as was done prior to the advent of test case generators.
An example of a conventional test program generator is the IBM tool, Genesys, which is disclosed in the document Model-Based Test Generation for Process Design Verification, Y. Lichtenstein et al., Sixth Innovative Applications of Artificial Intelligence Conference, August 1994, pp. 83-94. An updated version, of Genesys, known as Genesys-Pro, is a generic random test generator, targeted at the architectural level and applicable to any architecture.
Another conventional test program generator, AVPGEN, is disclosed in the document AVPGEN—A Generator for Architecture Verification Test Cases, A. Chandra, et al., IEEE Trans. Very Large Scale Integration (VLSI) Syst. 3, No. 2, pp. 188-200 (June 1995).
X-Gen, a model-based test-case generator, is described in the document X-Gen, a random test-case generator for systems and SoCs, R. Emek, et al., Seventh IEEE International High-Level Design Validation and Test Workshop (HLDVT 2002). This test generator is specialized for use with multiprocessor systems and systems on a chip (SoCs). X-Gen provides a framework and a set of building blocks for system-level test-case generation. Test program generation using X-Gen typically involves the resolution of constraints to make the tests legal and interesting for verification.
Varied strategies have been devised to influence or control the operation of test generators in order to achieve test coverage within a reasonable time and expenditure of resources. One of these strategies is the use of labeled transition systems to model the behavior of processes. For example, the patent document WO 2004/107087 proposes providing the specification of an application in the form of flow graphs. A computer system examines or traverses the flow graphs to generate various test paths. A user may then specify different input value combinations associated with each test path to generate a corresponding number of test cases, and thereby test the application exhaustively.
In another approach to test generation, the document Automatic Test Case Generation for OCL: a Mutation Approach, Pari Salis, Percy Antonio et al., United Nations University International Institute for Software Technology UNU-IIST and UNU-IIST Reports, Report No. 321, May 2005, proposes mutation of a specification, in order to model errors that can happen during the development process, followed by generation of test cases that cover the introduced errors. In this system, a language known as Object Constraint Language is used to express formal constraints in the context of a model.